Für unsere Untersuchungen zu NP-schweren Problemen haben wir uns das Steinerbaumproblem herausgesucht:

Steinerbäume bilden wegen ihrer kürzeren Gesamtkantenlänge eine attraktive Alternative zu herkömmlichen spannenden Bäumen. Leider ist das Problem, einen minimalen Steinerbaum zu finden (im Gegensatz zu dem Problem, einen minimalen aufspannenden Baum zu finden) NP-schwer; dies gilt sogar für scheinbar einfache Spezialfälle, wie z.B. bei Verwendung der Manhattan-Metrik. Nachdem wir in früheren Jahren schnelle Heuristiken entwickelt haben, die dem Optimum sehr nahe kommen (ca. 25 %), haben wir uns in der jüngsten Vergangenheit auf die Entwicklung von Algorithmen spezialisiert, die für kleinere Probleminstanzen das Optimum exakt berechnen; dabei haben wir einen Weltrekord aufgestellt; unsere Implementierung löst im momentanen Stadium l&oust unser Verfahren jedes Problem bis zur Größe 55 und viele größere Probleme bis zu 100 Punkten. Die bisher besten Programme konnten nur Probleme bis zu einer Größe von etwa 40 lösen.

Veröffentlichungen:

M.Kaufmann, S.Gao and K.Thulasiraman: ``On Steiner Minimal Trees in Grid Graphs and its Application to Homotopic Routing '', Journal of Circuits, Systems and Computers, Vol. 6, No. 1, pp. 1-13, 1996.

P.Berman, U.Fößmeier, M.Karpinski, M.Kaufmann, A.Zelikovsky: ``Approaching the 5/4 -- Approximation for Rectilinear Steiner Trees'', Proc. 2nd European Symposium on Algorithms (ESA'94), LNCS, pp. 60-71, Springer-Verlag, 1994.

U. Fößmeier, M. Kaufmann, A. Zelikovsky: ``Faster Approximation Algorithms for the Rectilinear Steiner Problem'', in print for Discrete & Computational Geometry.

U. Fößmeier and M. Kaufmann: ``Solving Rectilinear Steiner Tree Problems Exactly in Theory and Practice'', to appear in ESA 1997.